1. Field of the Invention
The present invention generally relates to the field of artificial intelligence and, more particularly, to adaptive mechanisms for increasing the speed of execution of sequential decisions. As used herein, artificial intelligence means that part of computer science concerned with designing intelligent computer systems. Such systems are finding increasing application in problem-solving, logical reasoning, language understanding, programming, learning, expert systems, robotics and vision.
2. Description of the Prior Art
Among the most important aspects to problem-solving methods in artificial intelligence are (1) representation and (2) search. The present invention is concerned with the efficiency of search in the decision making process. Search strategies in current practice typically have the following characteristics:
1. they use fixed control; PA1 2. they are insensitive to experience; and PA1 3. they do not exploit the usage pattern of the search program. PA1 adj(a,b). PA1 adj(a,c). PA1 adj(a,d). PA1 adj(a,e). PA1 adj(b,c). PA1 adj(b,d). PA1 adj(c,d). PA1 adj(e,f). PA1 conn(X,Y)&lt;-ne(X,Y)&adj(X,Y). PA1 conn(X,Y)&lt;-ne(X,Y)&adj(X,Z)&conn(Z,Y). PA1 conn(X,Y)&lt;-fail. PA1 I,I,I, . . . ,I (sequence of n I's), then the search trees traversed in the repetitive solution of the problem instances will be PA1 T(I),T(I),T(I), . . . ,T(I) (sequence of n T(I)'s). PA1 adj(a,e). PA1 adj(a,c). PA1 adj(a,d). PA1 adj(a,b). PA1 adj(b,c). PA1 adj(b,d). PA1 adj(c,d). PA1 adj(e,f). PA1 conn(X,Y)&lt;-ne(X,Y)&adj(X,Y). PA1 conn(X,Y)&lt;-ne(X,Y)&adj(X,Z)&conn(Z,Y). PA1 conn(X,Y)&lt;-fail.
Search strategies that use fixed control are inherently limited in achieving good run-time performance. A fixed search stategy is illustrated here by way of an example of pathfinding in a graph. Consider a directed graph (digraph for short) such as the one shown in FIG. 1 of the drawings. A program may be written in PROLOG to search for paths between specified pairs of nodes in the digraph. PROLOG is a computer program language which derives its name from PROgramming in LOGic and is a major artificial intelligence implementation language. See, for example, D. H. D. Warren, L. M. Pereira and F. Pereira, "PROLOG--The Language and Its Implementation Compared with LISP", Proceedings of the Symposium on Artificial Intelligence and Programming Languages (1977), published by the ACM. An example of such a program is shown below.
Suppose a top-down, left-to-right search strategy (i.e., depth-first search) with backtracking is used as provided by a Prolog system. Suppose the search program is queried whether a is connected to f by typing "&lt;-conn(a,f).". Then, execution of the search will involve the traversal of the search tree shown in FIG. 2(a) before a path is found from a to f. The sequence of nodes visited in the search process is shown by a dashed line in the forward direction and by a dotted line in the reverse direction. Each query of the form "&lt;-conn(a,f)." represents an instance of the set of problem inputs that may be presented to the search program. For an instance I of the problem, let the search tree traversed be denoted as T(I). The main characteristic to observe with regard to a fixed search strategy is the following. If the search program were given a repetitive sequence of problem instances of the form
With respect to I, if the search program were inefficient to begin with, then no matter how many times I is solved, the search program will be exactly as inefficient as it were before it solved the first instance of I. The search program using fixed control does not learn to improve its efficiency to take advantage of the fact that, in its experience, it has solved certain problem instances more frequently than certain other problem instances. We believe that for realistic problems, not all input instances are equally likely to occur. Assuming the set of problem instances encountered exhibit a nonuniform distribution, this can be exploited by search programs to optimize their average run-time performance.
A significant disadvantage of a fixed search strategy, such as the depth-first search provided by PROLOG, is that a programmer has to be aware of the fixed order in which the search will be conducted for various inputs. If the programmer is concerned with efficiency, then he is responsible for writing the program in such a way that the fixed search strategy will find solutions efficiently for the set of problem instances he wishes to solve. For instance, suppose the pathfinding program is predominately used for finding a path from a to f and rather infrequently used for finding paths between other pairs of nodes. Then, a good strategy for improving performance is to write the program such that the search involved in finding a path from a to f is made as efficient as possible even at the expense of increasing the search effort for finding paths between some other pairs of nodes. Knowing that PROLOG uses a fixed depth-first search strategy, the programmer could achieve the desired objective by simply rewriting the pathfinding program as follows:
The search tree traversed in finding a path from a to f is as shown in FIG. 2(b), and the search effort involved is efficient. The average performance can thus be improved.
In general, the task of organizing the program for efficient execution by a fixed search strategy is complicated for two reasons. First, for moderate to large-sized search programs, understanding the structure of search trees traversed for different problem instances soon becomes difficult. Second, and more important, the programmer typically would have no a priori knowledge of the workload; i.e., the relative frequencies with which different problem instances will be submitted to the program over the program's lifetime. The programmer will typically have knowledge only of what constitutes valid problem inputs. These drawbacks are intrinsic in the nature of any fixed search strategy. The subject invention is directed to approaches which overcome the limitations of a fixed search strategy.
In the prior art, U.S. Pat. No. 4,368,509 to Li discusses mechanisms for adaptive self-optimization. Li's patent is based on an algorithm that discovers dependencies among variables. His algorithm generates a sequence of tests that adaptively discovers the dependencies. Li's technique allows the algorithm to produce a set of test inputs on which observations are made. Then, according to a particular mathematical strategy, a new set of inputs is generated. However, for the same set of inputs submitted at different instants in time, the system is controlled in an identical manner resulting in exactly identical performance.
As will become clear from the description which follows, Li's patent differs from our invention in a very fundamental manner. The key characteristics of our invention are adaptive learning and capability for self-improvement of efficiency of systems embodied with our invention. This is achieved by keeping a prior history of search performance. If a sequence of identical problem inputs were submitted to a system embodied with our invention, the efficiency with which the problem instance is solved can vary from one instance of the problem to the next in a way that tends to minimize the search effort involved in solving the problem. This is achieved by the adaptive learning mechanisms of the present invention. In contrast, Li's patent does not possess the unique characteristic of the invention, namely, adaptively learning to improve efficiency in a systematic manner so that frequently encountered classes of problem instances are solved with improved efficiency as the system is used on a repeated basis.
U.S. Pat. No. 4,472,770 to Li is more general than the above-referenced patent to Li; however, the comments given above apply to this patent as well.
U.S. Pat. No. 4,210,962 to Marsh et al provides a demonstration that dynamic programming problems can be solved rapidly enough for use in real-time applications. Marsh et al describe a special purpose parallel computer to speed up the solution of dynamic programming problems. The parameters of the dynamic programming problem are supplied as inputs to the dynamic programming processor. The main issue addressed by this patent is fast computation of the optimal solution to problems. There is no learning and adaptation involved. The efficiency with which an instance of a dynamic programming problem is solved does not depend on history; i.e., how often the problem instance was solved before by the processor disclosed in the patent. Thus, there is a fundamental difference between the Marsh et al patent and our invention which always tends to bias the system toward the efficient solution of frequenty encountered problem instances.
U.S. Pat. No. 4,499,596 to Casey et al discloses the idea of adapting a system in a manner that is influenced by the sequence of inputs presented to the system. Casey et al describe the logic of an algorithm that has been used for efficient classification of characters in the context of optical character recognition systems. The process of classification is then used to generate compact coded vector representation of scanned characters. This can result in reduced storage and transmission requirements for facsimile application. The objectives of the Casey et al patent do not include optimization of classification time or storage requirements. Casey et al's scheme adapts in the sense that it is able to receive an arbitrary sequence of text characters, one at a time. Each character that is encountered for the first time is automatically assigned a class index. Any subsequent encounter of the same character will result in retrieval of the class index of the character for output. Thus, adaptation in the context of the Casey et al patent means ability to classify character strings that are seen by the system for the first time. It should be noted that the purpose of adaptation is not optimization of any specified objective function, such as classification time. The method of adaptation described in the Casey et al patent is based on appropriately extending a decision tree network representation whenever a new character is encountered. It is of a heuristic nature. The decision tree representation generated by the algorithm is one of many possible decision trees that may be used to classify characters. There is no formal theoretical basis provided for choosing among the many possible representations. There is no concept of learning in the Casey et al patent. Given identical character sequences at different time instants, the classification algorithm always executes identical steps and requires the same amount of time and storage for execution. The efficiency of the algorithm for solving a problem instance does not depend on whether the problem instance was solved previously. Thus, there is fundamental difference between the Casey et al patent and our invention.